package main

import (
	"fmt"
	"sort"
)

//#link: https://leetcode-cn.com/problems/can-you-eat-your-favorite-candy-on-your-favorite-day/
func main() {
	candiesCount := []int{
		16, 38, 8, 41, 30, 31, 14, 45, 3, 2, 24, 23, 38, 30, 31, 17, 35, 4, 9, 42, 28, 18, 37, 18, 14, 46, 11, 13, 19, 3, 5, 39, 24, 48, 20, 29, 4, 19, 36, 11, 28, 49, 38, 16, 23, 24, 4, 22, 29, 35, 45, 38, 37, 40, 2, 37, 8, 41, 33, 8, 40, 27, 13, 4, 33, 5, 8, 14, 19, 35, 31, 8, 8,
	}
	queries := [][]int{
		{43, 1054, 49},
	}
	fmt.Println(canEat(candiesCount, queries))
}

func canEat(candiesCount []int, queries [][]int) []bool {
	answer := make([]bool, len(queries))
	totalCandies := make([]int, len(candiesCount))
	totalCandies[0] = candiesCount[0]
	for i, c := range candiesCount {
		if i > 0 {
			totalCandies[i] = totalCandies[i-1] + c
		}
	}
	for i, q := range queries {
		//吃的最少糖果数
		min := q[1] + 1
		//吃的最多糖果数
		max := (q[1] + 1) * q[2]
		//吃0类型的最少糖果数
		cMin := 1
		if q[0] > 0 {
			cMin = totalCandies[q[0]-1] + 1
		}
		//吃q[0]类型要吃的最大糖果数
		cMax := totalCandies[q[0]]

		answer[i] = !(min > cMax || max < cMin)

	}
	return answer
}

func canEatBySearch(candiesCount []int, queries [][]int) []bool {
	answer := make([]bool, len(queries))
	totalCandies := make([]int, len(candiesCount))
	totalCandies[0] = candiesCount[0]
	for i, c := range candiesCount {
		if i > 0 {
			totalCandies[i] = totalCandies[i-1] + c
		}
	}
	for i, q := range queries {
		//q[0] 想吃到类型为q[0]的糖 ,q[1]天,q[2]最多吃的糖果
		//min:=
		min := sort.SearchInts(totalCandies, q[1]+1)
		if min == len(candiesCount) {
			answer[i] = false
			continue
		}
		max := sort.SearchInts(totalCandies, (q[1]+1)*q[2])
		if q[0] >= min && q[0] <= max {
			answer[i] = true
		}
	}
	return answer
}
